N = 8 	-- the size of chessboard

-- check if location (n, c) is safe
function isplaceok (queens, n, c)
	for i = 1, n - 1 do 	-- for each placed queen
		if (queens[i] == c) or 						-- same column
			 (queens[i] - i == c - n) or  	-- same diagonal
			 (queens[i] + i == c + n) then 	-- same diagonal
			return false
		end
	end
	return true 	-- safe location
end

-- print the chessboard
function printsolution (queens)
	for i = 1, N do 	-- each row
		for j = 1, N do -- each column
			io.write(queens[i] == j and 'X' or '-', ' ')
		end
		io.write('\n')
	end
	io.write('\n')
end

-- add queen into queens recursively
first_solution = 0 	-- control the program to stop after it outputs the first solution
function addqueen (queens, n)
	if n > N then
		if first_solution == 0 then
			printsolution(queens)
			first_solution = 1
		end
	else 	-- try to put the nth queen
		for c = 1, N do
			if isplaceok(queens, n, c) then
				queens[n] = c 	-- put the nth queen in column c
				addqueen(queens, n + 1)
			end
		end
	end
end

-- run the program
addqueen({}, 1)
